//1. find the kth smallest element in two sorted arrays
//2. find the kth largest element in two sorted arrays
//3. find the kth smallest element in three sorted arrays
#include <iostream>
#include <iterator>
#include <algorithm>
int k_min(int a[], int a_left, int a_right, int b[], int b_left, int b_right, int k) {
	while(a_left <= a_right && b_left <= b_right) {
		int a_mid = (a_left+a_right)/2;
		int b_mid = (b_left+b_right)/2;
		int a_left_size = a_mid-a_left+1;
		int b_left_size = b_mid-b_left+1;
		if(k >= a_left_size + b_left_size){
			if(a[a_mid] <= b[b_mid]) {
				a_left = a_mid+1;
				k -= a_left_size;
			}
			else { //a[a_mid] > b[b_mid]
				b_left = b_mid+1;
				k -= b_left_size;
			}	
		}
		else {//k < a_left_size + b_left_size
			if(a[a_mid] <= b[b_mid])
				b_right = b_mid-1;
			else
				a_right = a_mid-1;
		}

	}
	if(a_left > a_right)
		return b[k-1];
	else
		return a[k-1];
}

void test_k_min(){
	int a[] = {1};
	int b[] = {2};
	int m = sizeof(a)/sizeof(int);
	int n = sizeof(b)/sizeof(int);
	std::copy(a,a+m,std::ostream_iterator<int>(std::cout," ") ); std::cout << std::endl;
	std::copy(b,b+n,std::ostream_iterator<int>(std::cout," ") ); std::cout << std::endl;
	int k;
	while(std::cin>>k){
		std::cout << "the " << k << "th smallest element is " << k_min(a,0,m-1,b,0,n-1,k) << std::endl;
	}
}